#include <bits/stdc++.h>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x)
		: val(x)
		, left(NULL)
		, right(NULL)
	{
	}
};

class Solution {
	unordered_map<int, int> index;

public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
		int len = inorder.size();
		for (int i = 0; i < len; i++)
			index[inorder[i]] = i;
		return create(preorder, inorder, 0, len - 1, 0, len - 1);
	}

private:
	TreeNode* create(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_rigth) {
		if (pre_left > pre_right)
			return nullptr;

		int pre_root = pre_left,
			in_root = index[preorder[pre_root]];

		TreeNode* root = new TreeNode(preorder[pre_root]);
		int leftSize = in_root - in_left;
		root->left = create(preorder, inorder, pre_left + 1, pre_left + leftSize, in_left, in_root - 1);
		root->right = create(preorder, inorder, pre_left + leftSize + 1, pre_right, in_root + 1, in_rigth);

		return root;
	}
};

int main()
{
	return 0;
}
